package main

// 执行dk间距的排序
// 分组情况： 加入 dk等于2。 1 3 5 7 9.  2 4 6 8 10. 就是分成的两组
func ShellInsert(nums []int, dk int) {
	// 假设 dk 为3， 分为的三组同时排序
	// 0， 1， 2 为三组的开始元素下标。  i 初始为 dk为 3，代表下一组第一个元素
	for i := dk; i < len(nums); i++ {
		temp := nums[i]
		j := i
		for ; j >= dk && temp < nums[j-dk]; j -= dk {
			nums[j] = nums[j-dk]
		}
		nums[j] = temp
	}
}

// 希尔排序: 指定排序数组以及 间距dk
func ShellSort(nums []int, dk int) {
	for k := dk; k > 0; k-- {
		ShellInsert(nums, k)
	}
}
